package listbyorder.access101_200.test133;

import java.util.*;

/**
 * 克隆图
 *
 * @author code_yc
 * @version 1.0
 * @date 2020/6/11 9:42
 */
public class Solution1 {


    // 方法一： BFS深度优先遍历
    // 首先一遍BFS将所有的元素加入到map中
    // 第二遍遍历的时候，将map中的邻居节点都给填上
    public Node cloneGraph(Node node) {
        if (node == null) return node;

        Queue<Node> queue = new LinkedList<>();
        HashMap<Integer, Node> map = new HashMap<>();
        HashSet<Integer> visit = new HashSet<>();
        queue.offer(node);
        visit.add(node.val);
        // 第一次BFS
        while (!queue.isEmpty()) {
            Node cur = queue.poll();
            Node n = new Node();
            n.val = cur.val;
            n.neighbors = new ArrayList<Node>();
            map.put(n.val, n);
            for (Node temp : cur.neighbors) {
                if (visit.contains(temp.val)) {
                    continue;
                }
                queue.offer(temp);
                visit.add(temp.val);
            }
        }
        // 第二次BFS
        queue = new LinkedList<Node>();
        queue.add(node);
        visit = new HashSet<Integer>();
        visit.add(node.val);
        while (!queue.isEmpty()) {
            Node cur = queue.poll();
            for (Node neighbor : cur.neighbors) {
                map.get(cur.val).neighbors.add(map.get(neighbor.val));
                if (visit.contains(neighbor.val)) {
                    continue;
                }
                queue.offer(neighbor);
                visit.add(neighbor.val);
            }
        }
        return map.get(node.val);
    }
}
